package com.atguigu.substring;

public class Manacher {
    public static void main(String[] args) {
        Manacher manacher=new Manacher();
        System.out.println(manacher.normalAlgorithm("112131211"));
    }
    public int normalAlgorithm(String str){
        if(str.length()==0 || str==null){
            return 0;
        }
        StringBuilder sb=new StringBuilder();
        sb.append("#");
        for(int i=0;i<str.length();i++){
            sb.append(str.charAt(i));
            sb.append("#");
        }
        String s=sb.toString();
        int max=-1;
        for(int i=0;i<s.length();i++){
             int left=i-1;
             int right=i+1;
             int tmp=1;
             while(left>=0 && right<=s.length()-1){
                 if(s.charAt(left--)==s.charAt(right++)){
                     tmp+=2;
                     if(tmp>max){
                         max=tmp;
                     }
                 }else{
                     break;
                 }
             }
        }
        return max/2;
    }
}
